\documentclass[11pt]{article}
\usepackage{amsthm}
\usepackage{amsmath}

\newcommand{\set}[1]{\{#1\}}
\newcommand{\Sc}{\textrm{Sc}}
\newcommand{\Pc}{\textrm{Pc}}
\newcommand{\card}[1]{|#1|}
\newcommand{\length}{\textit{length}}

\newtheorem{lemma}{Lemma}

\begin{document}

\section{Destination-Tagged Dummy Messages for SP-dags}

\subsection{Node Behavior}
\label{sec:propbehavior}

We present a new algorithm, called the \emph{destination-tagged
  propagation algorithm}, for generating dummy messages so as to avoid
deadlock in SP-DAGs with filtering.  In our approach, the source node
of each component $H$ of an SP-DAG is responsible for preventing
deadlock on undirected cycles of $H$ that cross more than one of its
sub-components.  As we proved in the previous section, such cycles
inevitably include two disjoint directed paths from $H$'s source to
its sink.  To preempt deadlock, $H$'s source therefore generates dummy
messages directed specifically to its sink, and any nodes in between
source and sink simply propagate (i.e.\ forward) these messages. Since
a node can be a source for multiple distinct components at once, it
may need to send dummy messages that target multiple sinks.

A source node may need to send dummy messages differently on each of
its outgoing edges. Formally, we represent the dummy message schedule
of an edge $e$ as a set $[e] = \set{p_1, p_2, ..., p_k}$, where each
$p_i = (\tau_i, d_i)$ is a \emph{dummy interval-destination pair}.
$\tau_i$ represents an interval at which a dummy message must be sent,
while $d_i$ represents its destination.  We assume that the pairs of
set $[e]$ are ordered by increasing $\tau$.  The invariant is that if
$\tau_i < \tau_j$, then $d_j$ is a postdominator of $d_i$.  To track
the time between successive dummy messages to each destination, edge
$e$ also maintains a counter $c_i$ for each pair $p_i$.  The value of
counter $c_i$ ranges from 0 to $\tau_i$.
% FIXME: what if there is a tie between two pairs in [e], e.g. (tau,
% d1) and (tau, d2) s.t. d1 is an ancestor of d2? For the algorithm to 
% work, don't you need to order these so that (tau, d1) comes before
% (tau, d2)?

Each time node $X$ processes an incoming message, it acts as follows: 
\begin{itemize}

\item If the message is a dummy, and $X$ is not its destination, then
  propagate the message on all $X$'s outgoing edges, and zero out all
  counters on these edges.

% FIXME: do you really mean ``increment all counters'', or do you just
% increment the counters for edges on which a real message isn't sent?
% Need to precisely define behavior if X chooses to filter incoming
% message on some subset of its outgoing edges.

\item If the message is not a dummy, or is a dummy message with
  destination $X$, then increment all counters on all outgoing edges.
  If a counter $c_i$ on edge $e$ reaches its maximum value, then send
  a dummy message with destination $d_i$ along $e$, and zero out all
  counters $c_j$ with $j \leq i$ on that edge.

\end{itemize}


\begin{lemma} \label{lem:forward}
Let $H$ be a component of $G$ with source $X$ and sink $Y$.
If $X$ propagates an incoming dummy message, then that message
will reach $Y$.
\end{lemma}

\begin{proof}
The dummy message was generated by some super-component $H'$ of $H$
with sink $Z$, which by the properties of SP-DAGs must be either $Y$
or a successor of $Y$.  In either case, all paths from $X$ to $Z$
lead through $Y$, so $Y$ will eventually receive the dummy message.
\end{proof}

\begin{lemma} \label{lem:maxint}
Suppose that, for edge $e$ out of node $X$, pair $(\tau_i, d_i) \in
[e]$.  For each $\tau_i$ messages that $X$ receives, it sends at least
one dummy message along $e$ that will reach $d_i$.
\end{lemma}
\begin{proof}
Consider a span of $\tau_i$ consecutive messges received by $X$.  Before
these messages arrive, $c_i$ has some value $< \tau_i$.  One of two
cases will occur:
\begin{enumerate}
\item If all the messages are non-dummies or target $X$, then either
  counter $c_i$ will increase until it reaches $\tau_i$, triggering a
  dummy message to $d_i$, or some other counter $c_j$, $j > i$, will
  reach $\tau_j$, triggering a dummy message to $d_j$.  Since we have
  the invariant that $d_j$ is a postdominator of $d_i$, this message
  will pass through $d_i$.

\item If some message is a dummy that does not target $X$, then
      by Lemma \ref{lem:forward}, it is targeted to some
      successor of $d_i$ and so will pass through $d_i$.
\end{enumerate}

\end{proof}

%\begin{lemma}
%If an edge $e_1$ has a dummy message, then all edges that succeed this
%edge eventually forward this dummy message until it reaches its
%destination.
%\end{lemma}
%\begin{proof}
%From model.
%\end{proof}

\subsection{Computing dummy intervals}
\label{sec:dest-tagged-spdags}

\begin{enumerate}

\item We first recursively decompose $G$ according to the construction
  rules for SP-DAGs, using e.g.\ the linear-time recognition algorithm
  of Valdes, Tarjan, and Lawler~\cite{Valdes79}. The decomposition
  results in a tree $T$ whose leaves are single (multi-)edge graphs
  and whose internal nodes are labeled with the composition operators
  $\Sc$ or $\Pc$, such that applying the composition operations in
  post-order results in graph $G$. The size of this tree is $O(|G|)$.

\item For every component $H$ of $G$, we compute $L(H)$, which is the
  length of a shortest directed path (with buffer lengths as edge
  weights) from the source of $H$ to its sink. This calculation can be
  done bottom-up on the tree $T$ in $O(|G|)$ time.

\item We then compute the dummy intervals for each edge as described below. 

\end{enumerate}

For step 2 of the above procedure, the following algorithm allows us
to use the component tree $T$ to compute shortest paths from source to
sink for each component $H$ of $G$ in $O(|G|)$ time.  For a single
multi-edge $X\to Y$, we can compute a shortest path from $X$ to $Y$ in
time proportional to the number of edges.  Given shortest path lengths
$L(H_1)$ and $L(H_2)$ from source to sink in SP-DAGs $H_1$, $H_2$, we
can compute this length for their composition $H$ in constant time as
follows:
\begin{itemize}
 \item If $H = \Sc(H_1,H_2)$, $L(H) = L(H_1) + L(H_2)$.
 \item If $H = \Pc(H_1,H_2)$, $L(H) = \min( L(H_1), L(H_2) )$.
\end{itemize}

For step 3 above, we can compute all dummy intervals in
$O(\card{G}^2)$ time during a post-order traversal of $T$ as follows.
Let $H$ be a component of $G$.

\textbf{Case 1:} Say $H$ is a leaf of $T$ corresponding to a
multi-edge $X\to Y$.  We designate an interval $\tau$ for edge $e$ as
the minimum buffer size over all edges other than $e$ between $X$ and
$Y$, and set $[e] = \{ (\tau, Y) \}$.  If $X\to Y$ is only a single
edge, then $[e] = \{\}$.

\textbf{Case 2:} Say $H = \Sc(H_1,H_2)$.  Since $H_1$ and $H_2$ are
joined by a single articulation point, their composition creates no
new simple cycles.  The dummy intervals for edges in $H_1$ and $H_2$
do not change.

\textbf{Case 3:} Say $H = \Pc(H_1,H_2)$, where $X$ is $H$'s source and
$Y$ is $H$'s sink.  For each node $Z \in H - \set{X}$ with two
outgoing edges $e$ and $e'$, Lemma~\ref{lemma:sp1.2} proves that the
parallel composition introduces no new simple cycle that leaves $Z$
via $e$ and returns via $e'$.  Hence, the dummy intervals for these
nodes' outgoing edges do not change.  For the source $X$ itself, the
composition creates undirected cycles consisting of two directed paths
from $X$ to $Y$, as shown in Corollary \ref{corollary:sp1.3}.  Each
such cycle leaves $X$ via some $e$ in $H_1$ and returns via some $e'$
in $H_2$.  Recall that we precomputed $L(H_1)$ and $L(H_2)$ as the
total buffer lengths on some shortest (by total buffer length)
directed path from $X$ to $Y$ in $H_1$ and $H_2$, respectively.  Now
we compute new dummy intervals for each edge $e$ out of $X$ in $H_1$,
\[
[e] \leftarrow e \cup (L(H_2), Y).
\]
Similarly, for each edge $e'$ out of $X$ in $H_2$, we set a new interval
\[
[e] \leftarrow e \cup (L(H_1),Y).
\]

Now we do some postprocessing in order to remove extra dummy messages.
\begin{itemize}
\item If a particular edge $e$ has more than one interval with the
  same destination, we keep only the one with the smallest $\tau_i$.

\item If a particular edge has two pairs $p_i = (\tau_i, d_i)$ and
  $p_j = (\tau_j, d_j)$, such that $d_i$ postdominates $d_j$ and
  $\tau_i \leq \tau_j$, then we can remove $p_j$.

\item Now consider any edge $e$ starting at $X$, and say edge $e'$
  precedes it.  If $e'$ has any dummy intervals $(\tau_i, d_i)$, then
  we can remove all of $e$'s pairs $(\tau_j, d_j)$ where $\tau_j >
  \tau_i$ and $d_i$ postdominates $X$.  

ALTERNATIVE FORMULATION. Now consider two intervals $p_1$ and $p_2$,
such that $p_1$ originates at edge $e_1$ which starts at $X_1$ and
$p_2$ originates at edge $e_2$ which starts at $X_2$.  If $e_1$
preceedes $e_2$, $\tau_1 \leq \tau_2$, and $d_1$ postdominates $d_1$,
then we can remove $\tau_2$.
\end{itemize}

\begin{lemma}
If an edge has a pairs $p_i = (\tau_i, d_i)$ and $p_j = (\tau_j, d_j)$, 
and $\tau_i \leq \tau_j$, then $d_j$ is a postdominator of $d_i$. 
\end{lemma}
\begin{proof}
Due to condition 1, they can not be the same node.  Due to properties of SP-dags, one is a postdominator of the other.  If $d_i$ was a postdominator of $d_j$, then we would have removed $p_j$ due to step 2 above.
\end{proof}

The next lemma shows why it is ok to remove the pairs from step 3.  
\begin{lemma} \label{lem:thirdstep}
  Consider an edge $e$ starting at $X$, and say edge $e'$ starting at
  $Z$ precedes it.  Say $e$ has a pair $p_j = (\tau_j, d_j)$ and $e'$
  has a pair $p_i = (\tau_i, d_i)$ such that $d_i$ postdominates $X$
  and $\tau_j \geq \tau_i$.  Then the counter for the pair $p_j$ will
  never reach its maximum value.
\end{lemma}
\begin{proof}
Due to the properties of SP-dags, $Z$ is a predecessor of $X$, and $X$ can get a message with a particular index only if $Z$ only got it.  In addition, since $d_i$ postdominates $X$, every time $Z$ sends a dummy message for pair $p_i$, $X$ gets it, and when $X$ gets it, it zeroes out all of its dummy message counters.  Since the maximum interval between two dummy messages from $Z$ is $\tau_i$, the counter for $p_j$ will never reach $\tau_j$.
\end{proof}


\begin{lemma}\label{lem:postproc}
Consider any parallel component $H=\Pc(H_1,H_2)$ with source $X$ and
destination $Y$.  Let $L(H_1)$ be the shortest path from $X$ to $Y$
through $H_1$.  Consider any edge $e \in H_2$ that starts at $X$.  In
any time period that $X$ receives $L(H_1)$ messages, it sends (or
forwards) at least one dummy message on $e$ with destination $Y$ or a
successor of $Y$.
\end{lemma}
\begin{proof}
  Before the postprocessing, $(L(H_1), Y)$ would have been set as one
  of the pairs on $e$ due to the algorithm.  The first step or the
  second step of postprocessing only remove $(L(H_1), Y)$ if $X$ sends
  a more frequent dummy message to $Y$ or one of its predecessors.  As
  shown in Lemma~\ref{lem:thirdstep}, the third step only removes a
  pair if it will never be used.  Therefore, by
  Lemma~\ref{lem:maxint}, $X$ must also have sent at least one dummy
  message along $e$ that reached $Y$ every time it gets $L(H_2)$
  messages.
\end{proof}

\begin{lemma} \label{lem:correct}
If dummy messages are sent as described in Section~\ref{sec:propbehavior},
using the interval-destination pairs computed by the above procedure, 
then deadlock cannot occur in $G$.
\end{lemma}

\begin{proof}
  Suppose a deadlock does occur in $G$. Then there must be a blocking
  cycle $C$ in $G$.  Since $G$ is an SP-dag, $C$ lies in some smallest
  parallel component $H$ and consists of two directed paths $s_1$ and $s_2$
  joining $H$'s source $X$ to its sink $Y$.

  Suppose WLOG that path $s_1$ is empty and $s_2$ is full.  We can
  decompose $H$ into parallel sub-components $H_1$ and $H_2$ such that
  $s_1 \subseteq H_1$ and $s_2 \subseteq H_2$.  By construction,
  $\length(s_1) \geq L(H_1)$ and $\length(s_2) \geq L(H_2)$.

  Now consider the first edge $e$ in path $s_2$, which leaves source
  $X$.  This edge is in component $H_2$.  Lemma~\ref{lem:postproc}
  ensures that every time $X$ recieves $L(H_1)$ messages, it sends a
  dummy message along $e$.  For $s_2$ to fill, $X$ must have received
  and passed on at least $L(H_2)$ messages.  Hence, $s_1$ can not be
  empty, which contradicts our assumption that cycle $C$ is blocking.
\end{proof}

We round down all dummy intervals to the closest power of two and do the post-processing again.  This only sends dummy messages more frequently, and therefore does not change the correctness proof.

\subsection{Running Time}




\subsection{Optimality}



\begin{lemma}
  Only one dummy message with a particular interval $\tau$ passes
  through a particular edge.
\end{lemma}
\begin{proof}
  Suppose not.  Consider an edge $e$ such that two dummy messages with
  the same $\tau$ pass through it.  There are two cases.
\begin{enumerate}
\item The two messages are generated by the same node.  If they have
  the same destination, step 1 of postprocessing will remove them.  If
  they have different destinations, then one is a postdominator of
  another, and the one which is not will be removed.
\item The two messages are generated by different nodes $X$ and $Y$.
  Step 3 will remove the one that was generated by the later node.
\end{enumerate}
\end{proof}

\begin{lemma}
  Say a source node $X$ gets $M$ non-dummy messages, and has an
  outgoing edge $e$ with dummy message pairs $[e] = \set{p_1, p_2,
    p_3, ..., p_k}$, sorted by increasing $\tau$.  The maximum number
  of messages $X$ creates on this edge (not including the ones that it
  forwards) is at most $M/\tau_1$.
\end{lemma}
\begin{proof}
\end{proof}

For any edge $e$, let $H_e$ be the set of parallel components that
contain $e$.  For a parallel component $H \in H_e$, let $X$ be the
source and $Y$ be the sink.  Now consider an edge $e_X$ out of $X$
that that preceeds $e$.  Consider the smallest pair $p_X$ on $e_x$ that has
a destination that succeeds $e$ (or a destination that does not
preceed $e$).  Let the interval for this pair be $\tau_{X, e}$
\begin{lemma}
For a particular $X$, there may be multiple edges $e_X$ that satisfy the above criterion.  All of them have the same $\tau_X$.  That is, the $\tau_X$ is unique for each $X$.  
\end{lemma}
\begin{proof}
  Suppose not.  One of the edges $e_X$ has a pair $p_1 = (\tau_1,
  d_1)$ and $e'_x$ has a pair $p_2 = (\tau_2, d_2)$ where both $d_1$
  and $d_2$ succed $e$ and $\tau_1 \neq \tau_2$.  WLOG, say $\tau_1 >
  \tau_2$.  

  Now consider the minimal parallel component that contains $e$, $e_X$
  and $e_X'$.  The dummy pairs $p_1$ and $p_2$ both carry messages to
  either the sink of this parallel component or to one of its
  postdominators.  Therefore, the intervals were set considering the
  components in parallel with this component.  TODO: Finish this proof.
\end{proof}

\begin{lemma}
  Let $X_e$ be a set of source that create dummy messages that pass
  through a particular edge $e$, and for any $X \in X_e$, let
  $\tau_{X,e}$ be the interval as defined above.  Let $M_X$ be the
  number of messages processed by $X$.  The total number of dummy
  messages created by $X$ that pass through $e$ is at most $\sum_{X
    \in X_e} M_X/\tau_{X,e}$.
\end{lemma}
\begin{proof}
\end{proof}

Consider any static and oblivious algorithm with the following properties.
\begin{itemize}
\item Only the source of a component can originate dummy messages for
  the component's sink.
\item A node can not use information about its own filtering behavior
  in order to make decisions about dummy messages.
\item A node does not know the filtering behavior or the dummy message
  calculation of any other nodes.
\end{itemize}



\begin{lemma}
  Any static and oblivious algorithm must send at least $\max_{X \in
    X_e} M_X/2\tau_{X,e}$ messages through $e$ in order to prevent
  deadlock.
\end{lemma}
\begin{proof}
  Say that there is some node $X \in X_e$, such that it it processes
  $M_X$ nodes and $e$ gets fewer than $M_X/2\tau_{X,e}$ messages.  Let
  $d$ be the destination for the dummy interval corresponding to
  $\tau_{X,e}$.  

  Consider a path $s_1$ from $X$ to $d$ which goes through $e$ and starts at
  $e_X$.  Since the dummy interval was set as $\tau_{X,e}$, we know that there is some disjoint path $s_2$ from $X$ to $e$ with path length at most $\length(s) = 2\tau_{X,e}$.  Say the first edge of this path is $e'$.  

  Since the number of dummy messages on edge $e$ is small, there must
  be some interval of larger than $2\tau_{X,e}$ when node $X$ recieved
  $2\tau_{X,e}$ messages and there were no dummy messages on edge $e$.
  Say that node $X$ filters all of the $2\tau_{X,e}$ messages in this
  interval going on edge $e_X$ and does not filter any on edge $e'$.
  In addition, none of the nodes on path $s_2$ filter any messages.
  Since $X$ can not use its own or its successor's filtering history
  to send dummy messages, this is entirely possible.  Therefore, after
  $\length(s_2)$ messages, path $s_2$ will fill up.  Since $X$ has
  sent no messages along $e_X$, path $s_1$ will remain empty, since
  none of the other nodes on the path can send dummy messages without
  getting any real messages.  Therefore, there is a deadlock.
\end{proof}

Say an edge belongs to a set of parallel components $H_1, H_2,
H_3,..$.  Let $\mathcal{L}(H_e)$ be the maximum $L(H)$ among all these
components.  In addition, 







% Now we can sort the dummy intervals and remove superfluous ones as
% follows:
% \begin{itemize}
% \item Round down each interval to the nearest power of two.

% \item If a particular edge $e$ has more than one interval with the
%   same destination, we keep only the one with the smallest $\tau_i$.

% \item If a particular edge has two pairs $p_1 = (\tau_1, d_1)$ and
%   $p_2 = (\tau_2, d_2)$, such that $d_1$ postdominates $d_2$ and
%   $\tau_1 \leq \tau_2$, then we can remove $p_2$.

% \item Now consider any edge $e$ starting at $X$, and say edge $e'$
%   precedes it.  If $e'$ has any dummy intervals $(\tau_i, d_i)$, then
%   we can remove all of $e$'s pairs $(\tau_j, d_j)$ where $\tau_j >
%   \tau_i$ and $d_j$ postdominates $X$.  

% ALTERNATIVE FORMULATION. Now consider two intervals $p_1$ and $p_2$,
% such that $p_1$ originates at edge $e_1$ which starts at $X_1$ and
% $p_2$ originates at edge $e_2$ which starts at $X_2$.  If $e_1$
% preceedes $e_2$, $\tau_1 \leq \tau_2$, and $d_1$ postdominates $d_1$,
% then we can remove $\tau_2$.
% \end{itemize}

% \begin{lemma} \label{lem:optcorrect}
% The prior optimizations do not affect correctness.
% \end{lemma}
% \begin{proof}
% % FIXME: are condition numbers correct here?
%   The first condition only increases the number of messages sent.  The
%   second and third just remove extra dummy messages.  The third one
%   would actually never be used, since every time $X_1$ processes
%   $\tau_1$ messages, it will send a dummy message along $e_1$.  Since
%   $e_1$ precedes $e_2$, this message will get $X_2$, and hence
%   transmitted on $e_2$.  At this time, all counters will be zeroed
%   out.  Therefore, $p_2$ is superfluous.
% \end{proof}


% The disadvantage of the above formulation is that each node has to
% potentially maintain many counters for each edge.  If we maintain a
% single counter, we may have to do many division operations to
% calculate when to send dummy messages.  Alternatively, we can reduce
% the number of counters by increasing the dummy message frequency.  In
% particular, we can round down all dummy intervals to the nearest power
% of two.  This allows us to maintain a single counter, and use bit
% tricks to calculate when to send and using bit tricks to allow us to
% calculate when to send dummy messages more efficiently.

% \subsection{Old Power of Two Algorithm}

% The calculation of the dummy messages remains the same, except that we
% round everything down to the power of two.  Again, if the node is not
% a source or a sink, it transmits all dummy messages.  If it is a sink,
% it transmits all but the ones that are destined to it.  Now the source
% behaviour is different. Now we don't keep counters.  Instead, for each
% pair $p_i$, we keep the last index when a dummy message with
% destination $d_i$ was sent.  We denote this by $\l_i$.  
% \begin{itemize}
% \item If the node is processing a non-dummy message with index $i$,
%   where $i > \tau_i+ l_i$, then schedule a message with destination
%   $d_i$.



\section{Destination tagged dummy messages for SP-ladders}

\subsection{Node Behavior}

In SP-ladders, we will distinguish between two types of nodes.
\textit{Internal} nodes are those that are internal to a chord
  (component SP-dag) of the SP-ladder.  A corner node is one that is a
  source or a sink of a chord of the SP-ladder.  The internal nodes of
  SP-ladders behave in the same way as the SP-dag explanation.  Here
  we will explain how the corner nodes behave.

  An SP-ladder can be decomposed into its constituent SP-DAGs as shown
  in Figure~\ref{fig:contraction}, where each edge represents an
  SP-DAG directed the same way as the edge.  This simplified
  representation of an SP-ladder has two paths from the source $X$ to
  the sink $Y$ and the only nodes are corner nodes. For convenience,
  we assume the two paths go from top to the bottom and distinguish
  them as the ``left path'' and the ``right path''.  We mark the
  vertices that connect these paths to cross-links from top to bottom,
  with the vertices on the left labeled $u_0, u_1 ,u_2,\ldots,u_{k+1}$
  and the vertices on the right path from top to bottom labeled $v_0,
  v_1,v_2,\ldots,v_{k+1}$.  The source $X = u_0 = v_0$ and the sink $Y
  = u_{k+1} = v_{k+1}$.  This graph has $k$ cross-links, which are
  numbered from top to bottom as $K_1$ through $K_k$, and the SP-DAGs
  on the outer cycle are numbered $S_0$ through $S_k$ on the left and
  $D_0$ through $D_k$ on the right.  Note that in some cases, $u_i =
  u_{i+1}$ and then $S_k$ is a graph with a single
  node. Figure~\ref{fig:ladderDecomp} illustrates the general
  decomposition and this special case.

  The corner sinks simply forward any messages that are not intended
  for them along all their outgoing edges.  Corner source behavior is
  the only one that changes.  The corner sources have two kinds of
  edges: edges on cross links $K_i$ and edges on downlinks ($S_i$ or
  $D_i$).  An edge going out of a corner source $u_i$ has three types
  of dummy pairs.  (1) The dummy pairs for messages that stay within
  the chord for which $u_i$ is a source ($S_i$ for downlink, and
  $K_i$ for crosslink).  There are kept sorted by increasing $\tau$ as
  in the case of SP-dags.  (2) The dummy pairs for some $v_k$, where
  $k>i$, a corner node on the other side of the ladder.  (3) The dummy
  pairs for some $u_i$, where $k>i$, a corner node on the same side of
  the ladder.  The second and third are stored in separate list by
  increasing $k$.

  When a corner source $u_i$ recieves a non-dummy message, it it
  increments the counters for all of its outgoing pairs.  If a pair
  $(\tau_a, d_a)$ reach its maximum value, then a dummy message with
  destination $d_a$ is sent along that edge, and the counter is zeroed
  out.  If the destination is an internal destination, then it behaves
  in the same way as the SP-dag algorithm.  If the destination is
  external, then all the counters for the internal messages on that
  edge are zeroed out.
  In addition, the following occurs.
\begin{itemize}
\item If the edge is in a crosslink, and the destination is $v_k$ or
  $u_k$, then dummy messages to all $v_j$ $j\leq k$ are zeroed out.
\item If the edge is in a downlink, and the destination is $v_k$ or
  $u_k$, then all the $u_j$ $j\leq k$ are zeroed out.  
\end{itemize}
If the message is a dummy message, it takes the following actions.  If
$u_i$ is the desination, then no action need be taken.  If it must be
forwarded, then the destination is always another corner node, say $d_a$.  
\begin{itemize}
\item If the destination is some $u_k$, or $v_k$, $k>i$, \footnote{If
    there are two cross-links out of $u_i$, then we use the larger $i$
    to make this decision.} then the message is forwarded along all
  the downlink edges.  All the counters for all the internal dummy
  messages on these downlinks are zeroed out.  All the counters on external
  dummy messages on downlinks with destination $u_j$, $j\leq k$ are
  zeroed out.  If the destination is $v_k$ (on the opposite side),
  then the dummy messages going there are also zeroed out.  All the
  counters (on downlinks and crosslinks) that are not zeroed out are
  incremented.
\item If the destination is some $v_k$, $k = i$, \footnote{If there
    are two crosslinks from $i$, we forward along the one that is
    equal.}  then the message is forwarded along all the crosslink
  edges and the interval dummy message counters on that crosslink are
  zeroed out.  All the other counters are incremented.  Note that if
  the message is being forwarded, it can not be intended for any $v_k$
  where $k>i$.
\end{itemize}


\begin{lemma}
The following are true.
\begin{itemize}
\item If a corner source $u_i$ propagates (forwards) a dummy message
  along any edge of the crosslink $K_i$, it will reach $v_i$, and will
  go through all the internal sinks of $K_i$.  In addition if $u_i$
  propagates a dummy messgage along any edge of the downlink $S_i$, it
  will reach $u_{i+1}$ and will propagate through all the internal
  nodes of $S_i$.  
\item If a corner source $u_i$ sends or forwards a dummy 
  message along a downlink to some sink $u_k$ or $v_k$, where $k\geq i$,
  this message will go through all the sinks $u_j$, $i \leq j \leq k$.
\item If a corner source $u_i$ sends or forwards a dummy message along
  a cross link $K_i$ intended for $v_k$ or $u_k$, where $k\geq i$, it
  reaches all the nodes $v_j$, $i\leq j\leq k$.
\end{itemize}
\end{lemma}
\begin{proof}
The first condition follows from the structure of SP-ladders.  

\end{proof}

\begin{lemma} \label{lem:maxint}
Suppose that, for edge $e$ out of node $X$, pair $(\tau_i, d_i) \in
[e]$.  For each $\tau_i$ messages that $X$ receives, it sends at least
one dummy message along $e$ that will reach $d_i$.
\end{lemma}
\begin{proof}
  Consider a span of $\tau_i$ consecutive messges received by $X$.
  Before these messages arrive, $c_i$ has some value $< \tau_i$.  For
  each incoming message, one of the following will occur.  cases will
  occur:
\begin{enumerate}
\item The counter will be incremented until it reaches  $\tau_i$, triggering a
  dummy message to $d_i$.
\item The counter will be zeroed out because some other dummy message
  is sent or forwarded.  From Lemma~\ref{ladder-props}, the counter is
  zeroed out only if the dummy message sent or forwarded will pass
  through $d_i$.
\end{enumerate}
\end{proof}


\subsection{Calculating the dummy intervals}


\begin{enumerate}

\item Decompose the SP-ladder into the component SP-DAGs, identifying the
  $u_i$'s, $v_i$'s, $S_i$'s, $D_i$'s and $K_i$'s.  In
  addition, we mark each edge as either belonging to a cross-link or
  not.  This can be done in $O(\card{G})$ time.

\item Compute dummy intervals for all edges due to cycles
  internal to each chord, using the algorithm of
  Section~\ref{sec:dest-tagged-spdags}.

\item For all $H \in \bigcup_{0 \leq i \leq k} S_i \cup D_i \cup K_i$,
  compute $L(H)$, which is the length of the shortest path from $H$'s
  source to its sink (in terms of buffer sizes).  Again, this is done
  as shown in Section~\ref{sec:spdummy}.

\item Starting at the bottom of the SP-ladder, for each $u_i$, and for
  each potential sink $t$ of $u_i$, we compute $L_s(u_i,t)$, which is
  defined as the shortest directed path starting at $u_i$, going
  through $S_i$ and ending at $t$.  Similarly define $L_k(u_i, t)$ as
  the shortest directed path starting at $u_i$, going through $K_i$
  and ending at $t$. If $u_i$ is not the source of $K_i$, then we
  just set $L_k(u_i, t) = 0$.  We define $L_d(v_i, t)$ and $L_k(v_i, t)$ in a
  similar manner, and compute those too.

\item Using these $L$ values, we can update the dummy intervals for
  all edges that start at internal sources and at source $X$.  No other
  dummy intervals change.

\end{enumerate}

For step 1, we can decompose an SP-ladder into its constituent SP-DAGs
in $O(\card{G})$ time as follows: Identify an outer cycle $C$ for $G$
with left and right sides, using DFS in linear time. For each vertex
$u$ on the left side of $C$, determine (via DFS) whether any directed
path leaving $u$ encounters the right side of $C$ at some vertex $v$
before it encounters the left side again.  If so, the nodes and edges
on all such paths from $u$ to $v$ form a cross link.  Repeat for the
right side of $C$ to identify cross-links directed from right to left.
Now that we have identified all $u_i$'s and $v_i$'s, we can easily
compute $S_i$'s, $D_i$'s and $K_i$'s.

For step 4 above, we can compute $L_s(u_i, t)$ and $L_k(u_i, t)$
starting at the bottom of the SP-ladder.  
\begin{eqnarray*}
L_k(u_i, v_i) &=& L(K_i) \mbox{ if $u_i$ is the source of $K_i$} \\
&=& 0 \mbox{ otherwise}\\
L_k(v_i, u_i) &=& L(K_i) \mbox{ if $v_i$ is the source of $K_i$} \\
&=& 0 \mbox{ otherwise}\\
L_s(u_i, t) &=& L(S_i) +  \\
&& \left\{ \begin{array}{cc} 0, & \mbox{if $u_{i+1} =
      t$}\\      
                             L_s(u_{i+1}, t) & \mbox{otherwise}
                   \end{array}
                   \right. \\
L_k(u_i, t) &=& \left\{ \begin{array}{cc} 
                 L(K_i) + L_d(V_i,t) & \mbox{if $u_{i}$ is $K_{i}$'s source} \\   
                 0 & \mbox{otherwise}
                   \end{array}\right.
\end{eqnarray*}
The calculations for $v_i$ are analogous.  

Now for each edge $e$ that starts at $u_i$ in $S_i$, set dummy
intervals with gap as $L_k(u_i, t)$ and destination $t$.  Similarly
for edges that start in $K_i$.  

Now we do some postprocessing to remove some superfluous pairs of
dummy messages.  For the internal dummy pairs, we do the same
processing as SP-dags.  In addition, we if any edge $e$ has an
internal pair $p_a = (\tau_a, d_a)$ and an external pair $p_b =
(\tau_b, d_b)$, where $\tau_a \geq \tau_b$, then $p_a$ is removed.
For the external dummy messages, we do the following for the node
$u_i$.
\begin{itemize}
\item If a particular edge $e$ has more than one interval with the
  same destination, we keep only the one with the smallest $\tau$.

\item If a cross link edge has two pairs $p_a = (\tau_a, d_a)$ and
  $p_b = (\tau_b, d_b)$, such that $\tau_a \geq \tau_b$, $d_a = v_k$
  (on the opposite side) and $d_b = v_j$ or $d_b = u_j$ for $k\leq j$,
  then we can remove $p_a$, since any dummy message going to $d_b$
  must pass through $d_a$.

\item If a downlink edge has two pairs $p_a = (\tau_a, d_a)$ and $p_b
  = (\tau_b, d_b)$, such that $\tau_a \geq \tau_b$, $d_a = u_k$ (on
  the same side) and $d_b = v_j$ or $d_b = u_j$ for $j\geq k$, then we
  can remove $p_a$, since any dummy message going to $d_b$ must pass
  through $d_a$.

\item Say $u_i$ has a dummy pair $p_a = (\tau_a, d_a)$ on one of its
  downlink edges.  Say there is a node $u_j$, $j<i$, which has a downlink
  edge with dummy pair $p_b = (\tau_b, d_b)$, where $\tau_b \leq
  \tau_a$ and $d_b = u_k$ or $d_b = v_k$ with $k>i$.  If $d_a = u_l$
  with $l \leq k$, then $p_a$ can be removed.

\end{itemize}

\begin{lemma}\label{lem:intervals}
If there is an external cycle that starts at $u_i$ and ends at $t$.  Every time $u_i$ recieves $L_S(u_i, t)$ messages, it sends at least one dummy message with destination $t$ along all its crosslink edges.  Every time $u$ recieves $L_K(u_i,t)$ messages, it sends at least one dummy message along all its downlink edges.
\end{lemma}
\begin{proof}
Using the above procedure for setting intervals, to start with, every crosslink edge will have a dummy interval with $(L_K(u_i, t), t)$ set.  If this dummy interval was removed due to the first condition, a dummy message is sent to $t$ more frequently.  If it is removed due to the second condition, a dummy message is sent which is guaranteed to go through $t$.  
\end{proof}


\begin{lemma} \label{lem:ladder-correct}
If dummy messages are sent as described in Section~\ref{sec:propbehavior},
using the interval-destination pairs computed by the above procedure, 
then deadlock cannot occur in $G$.
\end{lemma}

\begin{proof}
  Suppose a deadlock does occur in $G$. Then there must be a blocking
  cycle $C$ in $G$.  WLOG, say that the blocking cycle starts at $u_i$
  and ends at some sink $t$, and one path from $u_i$ to $t$ goes
  through $K_i$ and another one goes through $S_i$.  Say that the path $s_1$
  through $K_i$ is full and the path $s_2$ through $S_i$ is empty.  

  We know that $\length(s_1) \geq L_K(u_i, t)$.  If we consider the
  first edge of path $s_2$, it leaves $u_i$ through its crosslink.
  From Lemma~\ref{lem:intervals}, $u_i$ sends a dummy message along
  this edge every time it gets $L_K(u_i,t)$ messages.  Since this
  message is propagated all the way to $t$, $s_2$ can not be
  completely empty, which contradicts our assumption that cycle $C$ is
  blocking.
\end{proof}





\end{document}
